class Solution:
    def roate(self, nums, k):
        """
        方法：使用切片方式旋转数组
        
        Args:
            nums: List[int], 需要旋转的数组
            k: int, 向右旋转的步数
            
        Returns:
            None, 原地修改数组
            
        Time: O(n)，其中 n 是数组长度，切片操作需要 O(n) 时间
        
        Space: O(n)，需要额外的数组空间来存储临时结果
        """
        length = len(nums)
        if length == 0 or k == 0:
            return
        k %= length
        nums[:] = nums[-k:] + nums[:-k]

    def rotate2(self, nums, k):
        """
        方法：使用环状替换方式旋转数组
        
        Args:
            nums: List[int], 需要旋转的数组
            k: int, 向右旋转的步数
            
        Returns:
            None, 原地修改数组
            
        Time: O(n)，其中 n 是数组长度，每个元素只会被移动一次
        
        Space: O(1)，只使用了常数级的额外空间
        """
        length = len(nums)
        if length == 0 or k == 0:
            return
        k %= length
        count = self.gcd(k, length)
        for start in range(count):
            current = start
            prev = nums[start]
            while True:
                next_idx = (current + k) % length;
                nums[next_idx], prev = prev, nums[next_idx]
                current = next_idx
                if start == current:
                    break        

    def gcd(self, x, y):
        """
        方法：计算两个数的最大公约数
        
        Args:
            x: int, 第一个数
            y: int, 第二个数
            
        Returns:
            int: x 和 y 的最大公约数
            
        Time: O(log(min(x,y)))，使用欧几里得算法
        
        Space: O(1)，只使用了常数级的额外空间
        """
        return x if y == 0 else self.gcd(y, x % y)
        

    def rotate3(self, nums, k):
        """
        方法：使用三次翻转的方式旋转数组
        
        Args:
            nums: List[int], 需要旋转的数组
            k: int, 向右旋转的步数
            
        Returns:
            None, 原地修改数组
            
        Time: O(n)，其中 n 是数组长度，需要进行三次翻转，每次翻转需要 O(n/2) 操作
        
        Space: O(1)，只使用了常数级的额外空间
        """
        length = len(nums)
        k %= length
        self.reverse(nums, 0, length - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, length - 1)

    def reverse(self, nums, i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1